//235.二叉搜索树的最近公共祖先
//https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/?envType=daily-question&envId=2024-02-25
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //如果root为空 或 是pq任意一个节点的祖先 则返回
        if(root == nullptr || root == p || root == q) return root;
        TreeNode* left = lowestCommonAncestor(root->left,p,q);
        TreeNode* right = lowestCommonAncestor(root->right,p,q);
        if(left == nullptr) return right;
        if(right == nullptr) return left;
        return root;
    }
};